Google Code Jam/2010/1A/b/b.cpp

   1 #include <algorithm>
   2 #include <iostream>
   3 #include <iterator>
   4 #include <sstream>
   5 #include <fstream>
   6 #include <cassert>
   7 #include <climits>
   8 #include <cstdlib>
   9 #include <cstring>
  10 #include <string>
  11 #include <cstdio>
  12 #include <vector>
  13 #include <cmath>
  14 #include <queue>
  15 #include <deque>
  16 #include <stack>
  17 #include <list>
  18 #include <map>
  19 #include <set>
  20
  21 using namespace std;
  22
  23 template <class T> string toStr(const T &x){
  24 stringstream s; s << x; return s.str();
  25 }
  26
  27 template <class T> int toInt(const T &x){
  28 stringstream s; s << x; int r; s >> r; return r;
  29 }
  30
  31 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  32 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  33 #define D(x) cout << #x " = " << (x) << endl
  34
  35 const double EPS = 1e-9;
  36 int cmp(double x, double y, double tol = EPS){
  37   return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  38 }
  39
  40 const int oo = INT_MAX / 2;
  41
  42 #define minimize(x, y) if ((y) < (x)) (x) = (y)
  43
  44
  45 int a[105];
  46
  47 int dp[105][256];
  48
  49 int D, I, M, n;
  50
  51 inline int inserts(int a, int b){
  52   if (b < a) swap(a, b);
  53   int diff = b - a;
  54   if (diff == 0) return 0;
  55   if (M == 0) return oo;
  56   return ((diff - 1) / M) * I;
  57 }
  58
  59 void solve(){
  60   scanf("%d%d%d%d", &D, &I, &M, &n);
  61   for (int i = 0; i < n; ++i){
  62     scanf("%d", a + i);
  63   }
  64
  65   for (int k = 0; k < 256; ++k){
  66     dp[0][k] = 0;
  67   }
  68
  69   for (int i = 1; i <= n; ++i){
  70     int item = a[i - 1];
  71     for (int k = 0; k < 256; ++k){
  72       dp[i][k] = oo;
  73       int extra = abs(k - item);
  74       for (int j = i - 1; j >= 0; --j){
  75         int deleted = i - j - 1;
  76         for (int p = 0; p < 256; ++p){
  77           minimize(dp[i][k], extra + inserts(p, k) + deleted * D + dp[j][p]);
  78         }
  79       }
  80     }
  81   }
  82
  83   // for (int i = 0; i <= n; ++i){
  84   //   for (int k = 0; k < 16; ++k){
  85   //     printf("dp[%d][%d] = %d\n", i, k, dp[i][k]);
  86   //   }
  87   // }
  88
  89   int ans = oo;
  90   for (int k = 0; k < 256; ++k){
  91     minimize(ans, dp[n][k]);
  92   }
  93   printf("%d\n", ans);
  94 }
  95
  96
  97 int main(){
  98   int T;
  99   scanf("%d", &T);
 100   for (int i = 0; i < T; ++i){
 101     printf("Case #%d: ", i + 1);
 102     solve();
 103   }
 104   return 0;
 105 }